package structure;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;

/**
 * 使用 邻接矩阵 表示的 无向无权图
 *
 * @author or2
 * @Description 学习
 * @create 2021年08月26日 时间: 16:54
 */
public class AdjMatrix {

    /**
     * 数据文件相对路径
     */
    public static final String PATH = "java" + File.separator + "data-structure" + File.separator + "src" + File.separator + "data" + File.separator;
    /**
     * 顶点的个数
     */
    private int V;
    /**
     * 边的个数
     */
    private int E;
    /**
     * 邻接矩阵
     */
    private int[][] adj;

    /**
     * 从文件中获取图的数据
     *
     * @param fileName 文件夹名称
     */
    public AdjMatrix(String fileName) {
        File file = new File(PATH + fileName);
        try (Scanner scanner = new Scanner(file)) {
            V = scanner.nextInt();
            if (V < 0) {
                throw new IllegalArgumentException("顶点个数不能小于0!");
            }
            adj = new int[V][V];
            E = scanner.nextInt();
            if (E < 0) {
                throw new IllegalArgumentException("边的个数不能小于0!");
            }

            for (int i = 0; i < E; i++) {
                int v1 = scanner.nextInt();
                int v2 = scanner.nextInt();
//                是否处理平行边?权值?
                checkVIndex(v1);
                checkVIndex(v2);
                adj[v1][v2] = 1;
                adj[v2][v1] = 1;
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    /**
     * 检测 当前顶点下标是否越界
     * @param vIndex 顶点下标
     */
    private void checkVIndex(int vIndex) {
        if (vIndex < 0 || vIndex >= V) {
            throw new IllegalArgumentException("顶点下标越界!");
        }
    }

    /**
     * 检测 两顶点间是否有边
     * @param v1 顶点①
     * @param v2 顶点②
     * @return 存在边 -> true<br/>否则 -> false
     */
    boolean hasEdge(int v1, int v2) {
        checkVIndex(v1);
        checkVIndex(v2);
        return adj[v1][v2] == 1;
    }

    /**
     * 查找该顶点的边
     * @param v 被查找的顶点
     * @return 该顶点的边
     */
    public ArrayList<Integer> adj(int v) {
        checkVIndex(v);

        ArrayList<Integer> vertexs = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            if (adj[v][i] == 1) {
                vertexs.add(i);
            }
        }
        return vertexs;
    }

    /**
     * 计算当前顶点的度
     * @param v 顶点
     * @return 顶点的度
     */
    public int degree(int v) {
        return adj(v).size();
    }

    @Override
    public String toString() {
        String str = "AdjMatrix{" + "\n" +
                "顶点个数 V=" + V +
                ",边的个数 E=" + E + "\n" +
                '}' + "\n";
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(str);

        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                stringBuilder.append(adj[i][j]).append(" ");
            }
            stringBuilder.append("\n");
        }

        return stringBuilder.toString();
    }
}
